#include "PreCompile.hpp"
#include "SuperGlob.hpp"
#include "gpathext.hpp"
#include "TmpAllocator.hpp"

namespace BuildNG
{
  static void super_glob_recursive(
    const Glib::ustring &cur_dir,
    const std::vector<Glib::ustring> &pattern_elements,
    int cur_pattern_elem,
    std::vector<Glib::ustring> &out,
    const IDirectoryTree &dir_tree);
  bool glob_compare(const Glib::ustring &pattern,const Glib::ustring &b);
  void tokenize_glob_pattern(const gchar *pattern,TmpArray<GlobToken> &out);
  static inline bool compare_beginning_to_token(const gchar **b_ptr,const gchar *b_end,const GlobToken &token);
  static bool glob_compare_recursive(const TmpArray<GlobToken> &tokens,int cur_token,
    const gchar *b_begin,const gchar *b_end);

  std::vector<Glib::ustring> super_glob(const Glib::ustring &pattern,const IDirectoryTree &dir_tree,int flags)
  {
    std::vector<Glib::ustring> elements = Glib::Path::split_into_elements(pattern);

    std::vector<Glib::ustring> ret;
    if(Glib::path_is_absolute(pattern))
    {
      super_glob_recursive(dir_tree.get_root(),elements,0,ret,dir_tree);
    }
    else
    {
      super_glob_recursive("",elements,0,ret,dir_tree);
    }

    if(flags & SuperGlobFlag_AbsolutePath)
    {
      for(int i = 0;i < (int)ret.size();i++)
      {
        if(!Glib::path_is_absolute(ret[i]))
        {
          Glib::ustring abs_path = Glib::build_filename(dir_tree.get_cur_dir(),ret[i]);
          abs_path = Glib::Path::canonicalize_path(abs_path);
          ret[i] = abs_path;
        }
      }
    }
    
    return ret;
  }

  static void super_glob_recursive(
    const Glib::ustring &cur_dir,
    const std::vector<Glib::ustring> &pattern_elements,
    int cur_pattern_elem,
    std::vector<Glib::ustring> &out,
    const IDirectoryTree &dir_tree)
  {
    Glib::RefPtr<IDirectoryTree::DirIt> it;
    if(cur_dir != "")
      it = dir_tree.get_dir_iterator(cur_dir);
    else
      it = dir_tree.get_dir_iterator(dir_tree.get_cur_dir());

    while(it->move_next())
    {
      const Glib::ustring &cur_child = it->get_cur();
      if(glob_compare(pattern_elements[cur_pattern_elem],cur_child))
      {
        Glib::ustring cur_path;
        if(cur_dir != "")
          cur_path = Glib::build_filename(cur_dir,cur_child);
        else
          cur_path = cur_child;

        if(cur_pattern_elem == (int)pattern_elements.size() - 1)
        {
          out.push_back(cur_path);
        }
        else
        {
          if(it->is_directory())
          {
            super_glob_recursive(cur_path,pattern_elements,
              cur_pattern_elem + 1,out,dir_tree);
          }
        }
      }
    }
  }

  bool glob_compare(const Glib::ustring &pattern,const Glib::ustring &b)
  {
    // tokenize the pattern    

    TmpArray<GlobToken> tokens;
    tokenize_glob_pattern(pattern.c_str(),tokens);

    return glob_compare_recursive(tokens,0,b.c_str(),b.c_str() + b.bytes());
  }

  void tokenize_glob_pattern(const gchar *pattern,TmpArray<GlobToken> &out)
  {
    GlobToken cur_token;
    cur_token.begin = pattern;
    
    const gchar *c = pattern;
    while(*c)
    {
      if(*c == '*' || *c == '?')
      {
        if(cur_token.begin != c)
        {
          cur_token.end = c;
          cur_token.is_wildcard = false;
          out.append(cur_token);
        }

        cur_token.begin = c;
        c++;
        cur_token.end = c;
        cur_token.is_wildcard = true;
        out.append(cur_token);

        cur_token.begin = c;
      }
      else if(c[0] == '.' && c[1] == '.' && c[2] == '.')
      {
        cur_token.end = c;
        if(cur_token.begin != c)
        {
          cur_token.end = c;
          cur_token.is_wildcard = false;
          out.append(cur_token);
        }

        cur_token.begin = c;
        c += 3;
        cur_token.end = c;
        cur_token.is_wildcard = true;
        out.append(cur_token);

        cur_token.begin = c;
      }
      else
        c++;
    }

    if(cur_token.begin != c)
    {
      cur_token.end = c;
      cur_token.is_wildcard = false;
      out.append(cur_token);
    }
  }

  bool GlobToken::operator == (const gchar *b) const
  {
    for(const gchar *a = begin;a != end;a++)
    {
      if(*a != *b)
        return false;
      b++;
    }

    return *b == 0;
  }

  static inline bool compare_beginning_to_token(const gchar **b_ptr,const gchar *b_end,const GlobToken &token)
  {
    const gchar *b = *b_ptr;
    for(const gchar *a = token.begin;
      a != token.end;a++)
    {
      if(b == b_end)
        return false;
      if(*a != *b)
        return false;

      b++;
    }
    *b_ptr = b;
    return true;
  }

  static bool glob_compare_recursive(const TmpArray<GlobToken> &tokens,int cur_token,
    const gchar *b_begin,const gchar *b_end)
  {
    const gchar *b = b_begin;
    while(cur_token < tokens.get_size())
    {
      if(tokens[cur_token] == "*" || tokens[cur_token] == "?")
      {
        int min_num_chars = 0;
        bool can_be_more = false;
        while(cur_token < tokens.get_size())
        {
          if(tokens[cur_token] == "*")
            can_be_more = true;
          else if(tokens[cur_token] == "?")
            min_num_chars++;
          else
            break;

          cur_token++;
        }

        if(b + min_num_chars > b_end)
          return false;

        if(cur_token == tokens.get_size())
        {
          if(can_be_more)
            return true;
          else
            return b + min_num_chars == b_end;
        }
        
        if(can_be_more)
        {
          b += min_num_chars;
          for(;b != b_end;b++)
          {
            const gchar *peek_ahead = b;
            if(compare_beginning_to_token(&peek_ahead,b_end,tokens[cur_token]))
            {
              if(cur_token + 1 == tokens.get_size())
                return peek_ahead == b_end;
              else
              {
                if(glob_compare_recursive(tokens,cur_token + 1,peek_ahead,b_end))
                  return true;
              }
            }
          }
          return false;
        }
        else
        {
          return glob_compare_recursive(tokens,cur_token,b + min_num_chars,b_end);
        }
      }
      else if(tokens[cur_token] == "...")
      {
        assert(!"Not implemented yet");
      }
      else
      {
        if(!compare_beginning_to_token(&b,b_end,tokens[cur_token]))
          return false;
      }

      cur_token++;
    }

    return true;
  }

  //////////
  // PhysDirTree
  PhysDirTree::PhysDirTree(const Glib::ustring &cur_dir)
  {
    this->cur_dir = cur_dir;
  }

  Glib::RefPtr<IDirectoryTree::DirIt> PhysDirTree::
    get_dir_iterator(const Glib::ustring &path) const
  {
    return Glib::RefPtr<IDirectoryTree::DirIt>(new PhysDirTreeIt(path));
  }

  Glib::ustring PhysDirTree::get_root() const
  {
#ifdef G_OS_WIN32
    return "c:\\";
#else
    return G_DIR_SEPARATOR_S;
#endif
  }

  Glib::ustring PhysDirTree::get_cur_dir() const
  {
    return cur_dir;
  }

  /////////////
  // PhysDirTree::PhysDirTreeIt
  PhysDirTree::PhysDirTreeIt::PhysDirTreeIt(const Glib::ustring &path)
    : dir(path)
  {
    state = State_NotInitiated;
  }

  bool PhysDirTree::PhysDirTreeIt::move_next()
  {
    assert(state != State_Ended);

    if(state == State_NotInitiated)
    {
      it = dir.begin();
      state = State_Valid;
    }
    else
    {
      assert(state == State_Valid);
      it++;
    }

    if(it == dir.end())
    {
      state = State_Ended;
      return false;
    }

    cur_value = *it;
    return true;
  }

  const Glib::ustring& PhysDirTree::PhysDirTreeIt::get_cur()
  {
    assert(state == State_Valid);
    return cur_value;
  }

  bool PhysDirTree::PhysDirTreeIt::is_directory()
  {
    assert(state == State_Valid);
    return Glib::file_test(cur_value,Glib::FILE_TEST_IS_DIR);
  }
  
  // globbing in the actual file system
  std::vector<Glib::ustring> super_glob(const Glib::ustring &pattern,const Glib::ustring &base_dir,int flags)
  {
    PhysDirTree dir_tree(base_dir);
    return super_glob(pattern,dir_tree,flags);
  }
}
